\documentclass{ctexart}
\bibliographystyle{IEEEtran}
\usepackage{booktabs}
\usepackage{url}
\usepackage{algorithm,algorithmic}
\usepackage{listings}
\usepackage{xcolor}
\usepackage{tikz}
\pagestyle{plain}
\title{排序算法类的实现}
\author{张祺\\信息与计算科学 2101  3210104145}
\date{2022年11月25日}
\begin{document}
\maketitle
\section{排序效率测试}
\subsection{n=10000,序列完全随机}
\begin{center}
  \begin{tabular}{|c|c|c|c|c|} \hline
    P & 0.01 & 0.1 & 0.9 & 0.99 \\ \hline
    堆排序 & 0.001472 & 0.001416 & 0.001494 & 0.0015 \\ \hline
    快速排序 & 0.000257 & 0.000219 & 0.000238 & 0.000226 \\ \hline
  \end{tabular}
\end{center}
\subsection{n=10000,序列分布连续}
\begin{center}
  \begin{tabular}{|c|c|c|c|c|} \hline
    P & 0.01 & 0.1 & 0.9 & 0.99 \\ \hline
    堆排序 & 0.001472 & 0.001487 & 0.001506 & 0.001641 \\ \hline
    快速排序 & 0.000257 & 0.000236 & 0.000243 & 0.000236 \\ \hline
  \end{tabular}
\end{center}
\subsection{n=10000,序列中大量数据重复}
\begin{center}
  \begin{tabular}{|c|c|c|c|c|} \hline
    P & 0.01 & 0.1 & 0.9 & 0.99 \\ \hline
    堆排序 & 0.000228 & 0.000375 & 0.001428 & 0.001401 \\ \hline
    快速排序 & 0.000552 & 0.000486 & 0.000318 & 0.000237 \\ \hline
  \end{tabular}
\end{center}
\subsection{n=50000,序列分布连续}
\begin{center}
  \begin{tabular}{|c|c|c|c|c|} \hline
    P & 0.01 & 0.1 & 0.9 & 0.99 \\ \hline
    堆排序 & 0.008789 & 0.00878 & 0.008966 & 0.008752 \\ \hline
    快速排序 & 0.001344 & 0.001442 & 0.001469 & 0.001378 \\ \hline
  \end{tabular}
\end{center}
\subsection{n=50000,序列中大量数据重复}
\begin{center}
  \begin{tabular}{|c|c|c|c|c|} \hline
    P & 0.01 & 0.1 & 0.9 & 0.99 \\ \hline
    堆排序 & 0.001311 & 0.002478 & 0.00831 & 0.008493 \\ \hline
    快速排序 & 0.003197 & 0.003133 & 0.001714 & 0.001413 \\ \hline
  \end{tabular}
\end{center}
\subsection{结论}
由上述测试样例可以看出，快速排序在处理大部分序列时的效率都要优秀于堆排序，会比堆排序低一个数量级，但是在处理有大量数据重复且有序度较低的序列时，快速排序反而陷入了劣势。
\section{快速排序优化}
\subsection{优化迭代操作}
在原先的快速排序当中，当我们遇到大量重复元素出现时，我们无法避免的对一元素值进行反复的操作，由此会浪费掉大量的时间与空间。因此我们在确定中枢值的位置后，将与中枢值相等的元素都移到中枢值两边，由此以减少下一次迭代的数组长度，提高实验效率。但是这种方法只能在待排序列中有大量重复元素时，很大程度上地提高实验效率，在序列基本随机时，反而会增加所需的时间。
\subsubsection{测试样例}
\begin{center}
  \begin{tabular}{|c|c|c|c|c|} \hline
    序列 & 有序序列 & 完全随机序列 & 全部重复序列 & 半数重复序列 \\ \hline
    优化前 & 0.000264 & 0.000236 & 0.486816 & 0.326488 \\ \hline
    优化后 & 0.000537 & 0.000567 & 0.079236 & 0.279069 \\ \hline
  \end{tabular}
\end{center}
\subsection{优化短数组迭代处理}
当序列长度较小时，再使用快速排序的迭代已经不是最“便宜”的算法，我们可以直接利用插入排序来处理短序列的问题，而现在我们来研究当序列为完全随机序列，排序效率最高的临界值。
\subsubsection{测试样例}
当n=100000：
\begin{center}
  \begin{tabular}{|c|c|c|c|c|c|} \hline
    短序列长度 & 5 & 10 & 15 & 20 & 25 \\ \hline
    所需时间 & 0.003077 & 0.003175 & 0.002722 & 0.002604 & 0.002762 \\ \hline
  \end{tabular}
\end{center}
当n=1000000时：
\begin{center}
  \begin{tabular}{|c|c|c|c|c|c|} \hline
    短序列长度 & 5 & 10 & 15 & 20 & 25 \\ \hline
    所需时间 & 0.037837 & 0.034621 & 0.031979 & 0.031856 & 0.032453\\ \hline
  \end{tabular}
\end{center}
由此可见，当待排序列为完全随机序列时，取临界值为20可以在一定程度上提高排序算法的效率。
\end{document}
